package class25_windowMaxMin;

import java.util.LinkedList;

class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int N = nums.length;
        int[] ans = new int[N-k+1];
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i=0;i<N;i++){

            while(queue.size()>0 && nums[i]>nums[queue.peekLast()]){
                queue.pollLast();
            }

            queue.add(i);

            int firstIndex = queue.peekFirst();
            if(i-firstIndex>=k){
                queue.pollFirst();
            }

            if(i>=k-1){
                ans[i-k+1] = nums[queue.peekFirst()];
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        int [] input = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] ans = maxSlidingWindow(input,k);
        System.out.println(ans);
    }
}
